#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>

#define MAX_ITEMS 320000
#define MAX_CAPACITY 1000000

// 物品结构体
typedef struct {
    int index;      // 物品编号
    int weight;     // 重量
    double value;   // 价值
} Item;

// 保存物品数据到CSV文件
typedef struct {
    int n;
    char filename[128];
} ItemFileInfo;

void save_items_csv(const char *filename, Item *items, int n) {
    FILE *fp = fopen(filename, "w");
    if (!fp) {
        printf("无法写入文件: %s\n", filename);
        return;
    }
    for (int i = 0; i < n; i++) {
        fprintf(fp, "%d,%d,%.2f\n", items[i].index, items[i].weight, items[i].value);
    }
    fclose(fp);
}

// 从CSV文件读取物品数据
int load_items_csv(const char *filename, Item *items, int n) {
    FILE *fp = fopen(filename, "r");
    if (!fp) return 0;
    int count = 0;
    while (count < n && fscanf(fp, "%d,%d,%lf", &items[count].index, &items[count].weight, &items[count].value) == 3) {
        count++;
    }
    fclose(fp);
    return count == n;
}

// 检查目录是否存在，不存在则创建
void ensure_dir(const char *dir) {
#if defined(_WIN32) || defined(_WIN64)
    _mkdir(dir);
#else
    mkdir(dir, 0755);
#endif
}

// 随机生成物品数据
void generate_items(Item *items, int n) {
    for (int i = 0; i < n; i++) {
        items[i].index = i + 1;
        items[i].weight = rand() % 100 + 1; // 1~100
        items[i].value = (rand() % 90100 + 10000) / 100.0; // 100~1000, 保留两位小数
    }
}

// 打印物品信息
void print_items(Item *items, int n) {
    printf("编号\t重量\t价值\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\t%.2f\n", items[i].index, items[i].weight, items[i].value);
    }
}

// 计时函数
long long current_time_ms() {
    struct timespec ts;
#if defined(_WIN32) || defined(_WIN64)
    // Windows下用clock()
    return clock() * 1000 / CLOCKS_PER_SEC;
#else
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1000LL + ts.tv_nsec / 1000000LL;
#endif
}

// 动态规划法求解0-1背包问题
typedef struct {
    int *selected; // 记录选择的物品
    double total_value;
    int total_weight;
    long long elapsed_ms; // 运行时间（毫秒）
} KnapsackResult;

// 保存背包算法结果到CSV文件
void save_knapsack_result_csv(const char *folder, const char *algo, int n, int capacity, Item *items, KnapsackResult result) {
    // 创建算法结果文件夹
    char dir[256];
    snprintf(dir, sizeof(dir), "%s/%s", folder, algo);
    ensure_dir(folder);
    ensure_dir(dir);
    // 构造文件名
    char filename[512];
    snprintf(filename, sizeof(filename), "%s/%s_%d_%d.csv", dir, algo, n, capacity);
    // 检查文件是否已存在
    FILE *fp = fopen(filename, "r");
    if (fp) {
        fclose(fp);
        // 文件已存在，直接返回
        return;
    }
    fp = fopen(filename, "w");
    if (!fp) {
        printf("无法写入结果文件: %s\n", filename);
        return;
    }
    // 写入表头
    fprintf(fp, "编号,重量,价值\n");
    // 写入被选中的物品
    for (int i = 0; i < n; i++) {
        if (result.selected[i]) {
            fprintf(fp, "%d,%d,%.2f\n", items[i].index, items[i].weight, items[i].value);
        }
    }
    // 写入总计信息
    fprintf(fp, "总重量,%d\n", result.total_weight);
    fprintf(fp, "总价值,%.2f\n", result.total_value);
    fprintf(fp, "耗时(ms),%lld\n", result.elapsed_ms);
    fclose(fp);
}

KnapsackResult dp_knapsack(Item *items, int n, int capacity) {
    KnapsackResult result;
    long long start = current_time_ms();

    // 一维 DP 数组
    double *dp = (double *)calloc(capacity + 1, sizeof(double));
    // 路径记录数组：select,当问题规模过大时会爆内存，无法记录选中的所有物品
    /* int **select = (int **)calloc(n + 1, sizeof(int*));
    for(int i=0;i<n;i++){
        select[i]=(int *)calloc(capacity + 1, sizeof(int));
    } */
    // 初始化
    for (int w = 0; w <= capacity; w++) {
        dp[w] = 0;
    }

    // 动态规划填充
    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= items[i].weight; w--) {
            long long new_val = dp[w - items[i].weight] + (long long)(items[i].value * 100); // 转换为整数避免浮点误差
            if (new_val > dp[w]) {
                dp[w] = new_val;
                //select[i][w] = 1; // 记录选择了第 i 个物品
            }
        }
    }
    result.elapsed_ms = current_time_ms() - start;
    printf("动态规化耗费时间为: %lld ms\n",result.elapsed_ms);
    // 回溯找出选中的物品
    int *selected = (int *)calloc(n, sizeof(int));
    int w = capacity;
    // 计算总重量
    int total_weight = 0;
    /* for(int i=0;i<n;i++){
        if(select[i][w]){
            selected[i] = 1;
            total_weight+=items[i].weight;
            w -= items[i].weight;
        }
    } */


    // 填充结果
    result.selected = selected;
    result.total_value = dp[capacity] / 100.0f; // 转换回浮点数
    result.total_weight = total_weight;

    // 释放内存
    free(dp);
    /* for(int i=0;i<n;i++){
        free(select[i]);
    }
    free(select); */

    // 保存结果到CSV
    save_knapsack_result_csv("output", "dp", n, capacity, items, result);

    return result;
}

// 输出选择的物品信息
double print_knapsack_result(Item *items, int n, KnapsackResult result) {
    printf("选择的物品编号\t重量\t价值\n");
    for (int i = 0; i < n; i++) {
        if (result.selected[i]) {
            printf("%d\t%d\t%.2f\n", items[i].index, items[i].weight, items[i].value);
        }
    }
    printf("总重量: %d\n", result.total_weight);
    printf("总价值: %.2f\n", result.total_value);
    return result.total_value;
}

// 回溯法求解0-1背包问题
void backtrack(int i, int n, int capacity, Item *items, int curr_weight, long long curr_value_int, int *curr_selected, long long *max_value_int, int *best_selected, int *best_weight) {
    if (i == n) {
        if (curr_value_int > *max_value_int) {
            *max_value_int = curr_value_int;
            *best_weight = curr_weight;
            for (int k = 0; k < n; k++) best_selected[k] = curr_selected[k];
        }
        return;
    }
    // 不选第i个物品
    curr_selected[i] = 0;
    backtrack(i + 1, n, capacity, items, curr_weight, curr_value_int, curr_selected, max_value_int, best_selected, best_weight);
    // 选第i个物品
    if (curr_weight + items[i].weight <= capacity) {
        curr_selected[i] = 1;
        backtrack(i + 1, n, capacity, items, curr_weight + items[i].weight, curr_value_int + (long long)(items[i].value * 100), curr_selected, max_value_int, best_selected, best_weight);
    }
}

KnapsackResult backtrack_knapsack(Item *items, int n, int capacity) {
    long long start = current_time_ms();
    int *curr_selected = (int *)calloc(n, sizeof(int));
    int *best_selected = (int *)calloc(n, sizeof(int));
    long long max_value_int = 0; // 使用整数避免浮点精度问题
    int best_weight = 0;
    backtrack(0, n, capacity, items, 0, 0, curr_selected, &max_value_int, best_selected, &best_weight);
    free(curr_selected);
    KnapsackResult result;
    result.selected = best_selected;
    result.total_value = max_value_int / 100.0; // 转换回浮点数
    result.total_weight = best_weight;
    result.elapsed_ms = current_time_ms() - start;
    // 保存结果到CSV
    save_knapsack_result_csv("output", "backtrack", n, capacity, items, result);
    return result;
}

// 蛮力法（穷举法）求解0-1背包问题
KnapsackResult brute_force_knapsack(Item *items, int n, int capacity) {
    long long start = current_time_ms();
    int max_state = 1 << n; // 2^n种组合
    long long max_value_int = 0; // 使用整数避免浮点精度问题
    int *best_selected = (int *)calloc(n, sizeof(int));
    int best_weight = 0;
    for (int state = 0; state < max_state; state++) {
        int total_weight = 0;
        long long total_value_int = 0; // 转换为整数
        for (int i = 0; i < n; i++) {
            if (state & (1 << i)) {
                total_weight += items[i].weight;
                total_value_int += (long long)(items[i].value * 100); // 转换为整数，保留两位小数
            }
        }
        if (total_weight <= capacity && total_value_int > max_value_int) {
            max_value_int = total_value_int;
            best_weight = total_weight;
            for (int i = 0; i < n; i++) {
                best_selected[i] = (state & (1 << i)) ? 1 : 0;
            }
        }
    }
    KnapsackResult result;
    result.selected = best_selected;
    result.total_value = max_value_int / 100.0; // 转换回浮点数
    result.total_weight = best_weight;
    result.elapsed_ms = current_time_ms() - start;
    // 保存结果到CSV
    save_knapsack_result_csv("output", "brute_force", n, capacity, items, result);
    return result;
}

// 贪心法求解0-1背包问题（按单位价值排序，尽量装满）
int cmp_item(const void *a, const void *b) {
    double r1 = ((Item *)a)->value / ((Item *)a)->weight;
    double r2 = ((Item *)b)->value / ((Item *)b)->weight;
    if (r1 < r2) return 1;
    else if (r1 > r2) return -1;
    else return 0;
}

KnapsackResult greedy_knapsack(Item *items, int n, int capacity) {
    long long start = current_time_ms();
    // 复制一份物品数组用于排序
    Item *sorted = (Item *)malloc(sizeof(Item) * n);
    for (int i = 0; i < n; i++) sorted[i] = items[i];
    qsort(sorted, n, sizeof(Item), cmp_item);
    int *selected = (int *)calloc(n, sizeof(int));
    int total_weight = 0;
    double total_value = 0.0;
    for (int i = 0; i < n; i++) {
        if (total_weight + sorted[i].weight <= capacity) {
            selected[sorted[i].index - 1] = 1; // 按原编号标记
            total_weight += sorted[i].weight;
            total_value += sorted[i].value;
        }
    }
    free(sorted);
    KnapsackResult result;
    result.selected = selected;
    result.total_value = total_value;
    result.total_weight = total_weight;
    result.elapsed_ms = current_time_ms() - start;
    printf("贪心法耗费时间为: %lld ms\n",result.elapsed_ms);
    // 保存结果到CSV
    save_knapsack_result_csv("output", "greedy", n, capacity, items, result);
    return result;
}

int main() {
    system("chcp 65001"); // 设置终端为UTF-8编码，防止中文乱码
    ensure_dir("data");
    
    // 大规模数据：用于动态规划法和贪心法
    int item_counts[] = {1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 20000, 40000, 80000, 160000, 320000};
    int capacities[] = {10000, 100000, 1000000};
    int num_cases = 15;
    int num_caps = 3;
    
    // 小规模数据：用于蛮力法和回溯法
    int small_item_counts[] = {20, 25, 30,};
    int small_capacities[] = {100, 300, 500};
    int num_small_cases = 3;
    int num_small_caps = 3;
    
    srand((unsigned int)time(NULL));
    
    // 处理大规模数据（动态规划法和贪心法）
    printf("=== 处理大规模数据（动态规划法和贪心法）===\n");
    for (int case_idx = 0; case_idx < num_cases; case_idx++) {
        int n = item_counts[case_idx];
        char filename[128];
        snprintf(filename, sizeof(filename), "data/items_%d.csv", n);
        Item *items = (Item *)malloc(sizeof(Item) * n);
        if (!items) {
            printf("内存分配失败！\n");
            continue;
        }
        // 检查文件是否存在并读取，否则生成并保存
        if (!load_items_csv(filename, items, n)) {
            printf("未找到%s，正在生成数据...\n", filename);
            generate_items(items, n);
            save_items_csv(filename, items, n);
            printf("已保存到%s\n", filename);
        } else {
            printf("已从%s读取数据\n", filename);
        }
        for (int cap_idx = 0; cap_idx < 3; cap_idx++) {
            int capacity = capacities[cap_idx];
            printf("正在处理: n=%d, capacity=%d\n", n, capacity);
            // 动态规划法
            dp_knapsack(items, n, capacity);
            // 贪心法
            greedy_knapsack(items, n, capacity);
        }
        free(items);
    }
    
    // 处理小规模数据（蛮力法和回溯法）
    printf("\n=== 处理小规模数据（蛮力法和回溯法）===\n");
    for (int case_idx = 1; case_idx < num_small_cases; case_idx++) {
        int n = small_item_counts[case_idx];
        char filename[128];
        snprintf(filename, sizeof(filename), "data/items_small_%d.csv", n);
        Item *items = (Item *)malloc(sizeof(Item) * n);
        if (!items) {
            printf("内存分配失败！\n");
            continue;
        }
        // 检查文件是否存在并读取，否则生成并保存
        if (!load_items_csv(filename, items, n)) {
            printf("未找到%s，正在生成数据...\n", filename);
            generate_items(items, n);
            save_items_csv(filename, items, n);
            printf("已保存到%s\n", filename);
        } else {
            printf("已从%s读取数据\n", filename);
        }
        for (int cap_idx = 0; cap_idx < num_small_caps; cap_idx++) {
            int capacity = small_capacities[cap_idx];
            printf("正在处理: n=%d, capacity=%d\n", n, capacity);
            // 回溯法
            backtrack_knapsack(items, n, capacity);
            // 蛮力法
            brute_force_knapsack(items, n, capacity);
        }
        free(items);
    }
    
    printf("所有算法结果已批量生成并保存完毕。\n");
    return 0;
}
